package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * <p>你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换
 */
public class Test24 {

    ListNode newHead = new ListNode();
    ListNode tail = newHead;

    public ListNode change(ListNode head){
        if (head == null){
            return head;
        }
        ListNode pre = head;
        List<ListNode> list = new ArrayList<>();
        while (pre != null){
            list.add(pre);
            pre = pre.next;
        }
        int size = list.size();
        int count = size/2;
        int temp = 0;
        while (temp <count){
            insert(list.get(2 * temp +1));
            insert(list.get(2 * temp ));
            temp++;
        }
        if (size % 2 ==1){
            // 说明是奇数
            insert(list.get(size-1));
        }
        tail.next = null;
        return newHead.next;
    }

    public void insert(ListNode node){
        tail.next = node;
        tail = node;
    }



    public ListNode exchange2(ListNode head){
        if (head == null){
            return null;
        }
        ListNode pre = head;
        while (pre != null){
            ListNode next = null;
            if (pre.next != null){
                next = pre.next.next;
            }
            ListNode now = pre.next;
            if (now != null){
                insert(now);
                insert(pre);
            }else {
                insert(pre);
            }
            pre = next;
        }
        tail.next = null;
        return newHead.next ;
    }
}


class Demo24{
  public static void main(String[] args) {
    Test24 t = new Test24();
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);
    ListNode change = t.exchange2(head);
    while (change!= null){
      System.out.println("val="+change.val);
      change = change.next;
    }

  }
}